package JZOffer;

/**
 * 剑指 Offer 13. 机器人的运动范围
 * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
 * 一个机器人从坐标 [0, 0] 的格子开始移动，
 * 它每次可以向左、右、上、下移动一格（不能移动到方格外），
 * 也不能进入行坐标和列坐标的数位之和大于k的格子。
 * 例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。
 * 但它不能进入方格 [35, 38]，因为3+5+3+8=19。
 * 请问该机器人能够到达多少个格子？
 * **/

//规律：在搜索过程中，如果下方格子与右方格子不符合要求，则向上或者向左返回上一个格子

    //方案一
class Solution13_1 {
    private int sum;
    public int movingCount(int m, int n, int k) {
        sum = 0;
        boolean[][] vis = new boolean[m][n];
        solve(0, 0, m, n, vis, k);
        return sum;
    }

    private int cul(int x, int y) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        while (y != 0) {
            res += y % 10;
            y /= 10;
        }
        return res;
    }

    public void solve(int x, int y, int m, int n, boolean[][] vis, int k) {
       if (x < 0 || y < 0 || x >= m || y >= n || vis[x][y] || cul(x, y) > k) return;

        // 当前位置（x，y）是可以走的，那么就从当前位置往四个方向移动即可
        vis[x][y] = true;
        sum++;
        solve(x+1, y, m, n, vis, k);
        solve(x-1, y, m, n, vis, k);
        solve(x, y+1, m, n, vis, k);
        solve(x, y-1, m, n, vis, k);
    }
}

//方案二
class Solution13_2 {
    private int cul(int x, int y) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        while (y != 0) {
            res += y % 10;
            y /= 10;
        }
        return res;
    }

    public int movingCount(int m, int n, int k) {
        int res = 1;
        boolean[][] vis = new boolean[m][n];
        vis[0][0] = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (cul(i, j) <= k) {
                    if (i - 1 >= 0 && vis[i - 1][j]) {
                        res++;
                        vis[i][j] = true;
                    } else if (i + 1 < m && vis[i + 1][j]) {
                        res++;
                        vis[i][j] = true;
                    } else if (j - 1 >= 0 && vis[i][j - 1]) {
                        res++;
                        vis[i][j] = true;
                    } else if (j + 1 < n && vis[i][j + 1]) {
                        res++;
                        vis[i][j] = true;
                    }
                }
            }
        }
        return res;
    }
}



